/* libwatopt++ - Optimization Toolkit
 *
 * Copyright (c) 2007 Christopher Alexander Watford
 * <christopher.watford@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 * $Id: hill_climber.cpp 2 2007-05-06 18:01:15Z christopher.watford $
 */

#include <limits>
#include <vector>
#include <algorithm>

#include <opt.hpp>
#include <hill_climber.hpp>

#include "utils.hpp"

namespace watopt
{
   //
   // HillClimberOpt
   //

   HillClimberOpt::HillClimberOpt(size_t maxSteps)
      : _m_Steps(maxSteps)
   {
   }

   HillClimberOpt::~HillClimberOpt(void)
   {
   }

   void
   HillClimberOpt::Initialize(IFitnessImplementation* guess)
   {
      _m_Best = guess;
   }
   	
	IFitnessImplementation*
   HillClimberOpt::Solve(void)
   {
      if(NULL == _m_Best)
         return NULL;

      std::vector<IFitnessImplementation*> neighbors;
      std::vector<IFitnessImplementation*>::iterator it;
      double bestFit = _m_Best->Fitness();
      for(size_t kk = 0; kk < _m_Steps; kk++)
      {
         double bestNeighbor = bestFit;
         IFitnessImplementation *best = _m_Best;
         
         // find the best neighbor
         _m_Best->Neighbors(neighbors);
         for(it = neighbors.begin(); it != neighbors.end(); ++it)
         {
            double fit = (*it)->Fitness();
            if(fit < bestNeighbor)
            {
               best = (*it);
               bestNeighbor = fit;
            }
         }

         // clean up
         for(it = neighbors.begin(); it != neighbors.end(); ++it)
         {
            if((*it) != best)
               delete (*it);
         }
         neighbors.clear();

         // if none of our neighbors are better, stop
         if(best == _m_Best)
            break;

         delete _m_Best; // clean up the old best solution
         _m_Best = best;
         bestFit = bestNeighbor;
      }

      return _m_Best;
   }

   void
   HillClimberOpt::GetSolutions(
      std::vector<IFitnessImplementation*>& solutions) const
   {
      solutions.push_back(_m_Best);
   }

   //
   // GreedyHillClimberOpt
   //

   GreedyHillClimberOpt::GreedyHillClimberOpt(size_t maxSteps)
      : _m_Steps(maxSteps), HillClimberOpt(maxSteps)
   {
   }

   GreedyHillClimberOpt::~GreedyHillClimberOpt(void)
   {
   }

   void
   GreedyHillClimberOpt::Initialize(IFitnessImplementation* guess)
   {
      _m_Best = guess;
   }
   	
	IFitnessImplementation*
   GreedyHillClimberOpt::Solve(void)
   {
      if(NULL == _m_Best)
         return NULL;

      std::vector<IFitnessImplementation*> neighbors;
      std::vector<IFitnessImplementation*>::iterator it;
      double bestFit = _m_Best->Fitness();
      for(size_t kk = 0; kk < _m_Steps; kk++)
      {
         double bestNeighbor = bestFit;
         IFitnessImplementation *best = _m_Best;
         
         // find the first best neighbor
         _m_Best->Neighbors(neighbors);
         for(it = neighbors.begin(); it != neighbors.end(); ++it)
         {
            double fit = (*it)->Fitness();
            if(fit < bestNeighbor)
            {
               delete _m_Best; // clean up the old best solution
               best = (*it);
               _m_Best = (*it);
               bestFit = fit;
               break;
            }
         }

         // clean up
         for(it = neighbors.begin(); it != neighbors.end(); ++it)
         {
            if((*it) != _m_Best)
               delete (*it);
         }
         neighbors.clear();

         // if none of our neighbors are better, stop
         if(best == _m_Best)
            break;
      }

      return _m_Best;
   }

   void
   GreedyHillClimberOpt::GetSolutions(
      std::vector<IFitnessImplementation*>& solutions) const
   {
      solutions.push_back(_m_Best);
   }


   //
   // RandomRestartHillClimberOpt
   //

   RandomRestartHillClimberOpt::RandomRestartHillClimberOpt(size_t maxTries,
      HillClimberOpt *climber)
      : _m_MaxTries(maxTries), _m_Climber(climber)
   {

   }
	
   RandomRestartHillClimberOpt::~RandomRestartHillClimberOpt(void)
   {
   }
   	
	IFitnessImplementation*
   RandomRestartHillClimberOpt::Solve(void)
   {
      _m_Solutions.clear();

      _m_Best = NULL;
      double bestFit = 0.0; // to stop warnings

      for(size_t kk = 0; kk < _m_MaxTries; kk++)
      {
         // resart the climber with a random solution
         _m_Climber->Initialize(Generate());

         // solve using the climber
         IFitnessImplementation *current = _m_Climber->Solve();
         double curFit = current->Fitness();

         // if this is the first solution, or the best so far
         // take it
         if((NULL == _m_Best) || (curFit < bestFit))
         {
            delete _m_Best; // clean up the old best solution, ok if NULL

            _m_Best = current;
            bestFit = curFit;
         }

         // save that solution
         _m_Solutions.push_back(current);
      }

      // sort the solutions we came up with
      std::sort(_m_Solutions.begin(), _m_Solutions.end(),
         IFitnessImplementation::FitnessPtrComp());

      return _m_Best;
   }

   void
   RandomRestartHillClimberOpt::GetSolutions(
      std::vector<IFitnessImplementation*>& solutions) const
   {
      solutions.insert(solutions.end(), _m_Solutions.begin(),
                           _m_Solutions.end());
   }
}
